package graph.base.minpath;

import graph.GraphNode;
import graph.graphtype.NoDirectWeightGraph;

import java.util.Stack;

/**
 * @author: 26233
 * @create: 2021-11-16 17:38:58
 * @Description
 *
 * 点对点最短路径Floyd (所有点之间的最短路)
 * 原理：
 *  1、基本思想：节点n1->n2直连的权重w1和节点n1通过nx到n2(即n1->nx->n2)的权重w2 + w3之间选择较小的权重
 *  2、所需的变量：
 *      图的邻接矩阵
 *      表示最短路径值的矩阵d[][]，初始为邻接矩阵，不直接相邻给一个较大的值
 *      表示可回溯路径的矩阵p[][],表示到达该点的前一个节点
 *
 *  3、根据图的定义式进行遍历所有节点并更新d和p矩阵
 *      从0->n遍历所有k节点
 *          从0->n遍历所有i节点
 *              从0->n遍历所有j节点
 *                  if(d[i][k] + d[k][j] < d[i][j]){
 *                         d[i][j] = d[i][k] + d[k][j];
 *                         p[i][j] = k;
 *                   }
 *
 *  d[i][k] + d[k][j]: i -> k -> j
 *
 *
 **/

public class Floyd {

    NoDirectWeightGraph g;

    int[][] d;
    int[][] p;

    public Floyd(NoDirectWeightGraph g) {
        this.g = g;

        d = new int[g.table.length][g.table.length];
        p = new int[g.table.length][g.table.length];
    }

    public void floyd(){

        // d: 邻接矩阵表示

        for (int i = 0; i < g.table.length; i++){
            GraphNode tempNode = g.table[i].next;
            while (tempNode != null){
                d[i][tempNode.id] = tempNode.edgeNode.getWeight(i)[1];
                tempNode = tempNode.next;
            }
        }

        for (int i = 0; i < g.table.length; i++){
            for (int j = 0; j < g.table.length; j++){
                p[i][j] = -1;

                if (d[i][j] == 0 && i != j){
                    d[i][j] = Integer.MAX_VALUE / 2;// 加法溢出注意！！！
                }
            }
        }

        for (int k = 0; k < g.table.length; k++){// 中间点 k
            for (int i = 0; i < g.table.length; i++){
                for (int j = 0; j < g.table.length; j++){
                    if(d[i][k] + d[k][j] < d[i][j]){
                        d[i][j] = d[i][k] + d[k][j];
                        p[i][j] = k;
                    }
                }
            }
        }

        System.out.println("======================");

        printPath();

    }

    private void printPath() {

        for (int i = 0; i < g.table.length; i++){
            System.out.println("------------------------");
            System.out.println("src: " + i);
            for (int j = 0; j < g.table.length; j++){
                if (i != j){
                    System.out.printf("%d to %d, min = %d, path: ", i, j, d[i][j]);
                    Stack<Integer> r = new Stack<>();
                    r.push(j);
                    int pre_index;
                    int pre = p[i][j];
                    while (pre != -1){
                        pre_index = p[i][j];
                        r.push(pre_index);
                        pre = p[i][pre_index];
                    }
                    r.push(i);
                    while (!r.isEmpty()){
                        Integer n = r.pop();
                        if (!r.isEmpty()){
                            System.out.print(n + "->");
                        }else {
                            System.out.print(n);
                        }
                    }
                    System.out.println();
                }
            }
            System.out.println("\n------------------------");
        }

    }

    public static void main(String[] args) {

        int[][] edges = new int[][]{{0, 1, 3}, {0, 2, 5}, {0, 4, 1},
                {1, 0, 3}, {1, 3, 1}, {2, 0, 5}, {2, 3, 2}, {2, 4, 4}, {3, 1, 1},
                {3, 2, 2}, {3, 4, 3}, {4, 0, 1}, {4, 2, 4}, {4, 3, 3}};
        int[] data = new int[]{1, 2, 3, 4, 5};
        NoDirectWeightGraph g = new NoDirectWeightGraph(data.length, data);
        g.generateGraph(edges);

        new Floyd(g).floyd();

    }

}
